package algorithm;

public class BinaryTree {

    Node tree;

    public void insert(int value){
        if (tree==null){
            tree=new Node(value);
            return;
        }

        Node p=tree;
        while (p!=null){
            if (value>p.data){
                if (p.right==null){
                    p.right=new Node(value);
                    return;
                }
                p=p.right;
            }else if(value<p.data){
                if (p.left==null){
                    p.left=new Node(value);
                    return;
                }
                p=p.left;
            }
        }
    }

    public Node find(int value){
        if (tree==null){
            return null;
        }

        Node p=tree;
        while(p!=null){
            if (value>p.data){
                p=p.right;
            }else if (value<p.data){
                p=p.left;
            }else{
                return p;
            }
        }

        return null;
    }

    public void delete(int value){
        Node p=tree;
        Node parent=null;

        while (p!=null && p.data!=value){
            if (value>p.data){
                parent=p;
                p=p.right;
            }else if (value<p.data){
                parent=p;
                p=p.left;
            }
        }

        if (p==null){
            return;
        }

        if (p.left!=null&&p.right!=null){
            Node tmpP=p.right;
            Node tmpParent=p;
            while(tmpP.left!=null){
                tmpParent=tmpP;
                tmpP=tmpP.left;
            }

            p.data=tmpP.data;
            p=tmpP;
            parent=tmpParent;
        }

        // 如果p结点下面有一个或没有孩子
        Node child;
        if (p.left!=null){
            child=p.left;
        }else if(p.right!=null){
            child=p.right;
        }else {
            child=null;
        }

        if (parent==null){
            tree=child;
        }else if (parent.right==p){
            parent.right=child;
        }else if(parent.left==p){

        }
    }

    public void preOrder(Node node){
        if (node==null)
            return;
        System.out.println(node.data);
        preOrder(node.left);
        preOrder(node.right);
    }

    public void inOrder(Node node){
        if (node==null)
            return;

        inOrder(node.left);
        System.out.println(node.data);
        inOrder(node.right);
    }

    public void postOrder(Node node){
        if (node==null)
            return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.data);
    }

    public static class Node{
        int data;
        Node left;
        Node right;

        public Node(int data){
            this.data=data;
        }
    }
}
